Przejdź do zawartości

Równanie rekurencyjne

Z Wikipedii, wolnej encyklopedii

Równanie rekurencyjnerównanie, które definiuje ciąg w sposób rekurencyjny.

Rozwiązanie rekurencji

[edytuj | edytuj kod]

Jest to postać jawna (iteracyjna) równania rekurencyjnego opisującego daną rekursję.

W większości przypadków, przy zastosowaniu odpowiednio zaawansowanego aparatu algebraicznego można uzyskać dokładne rozwiązanie równania/nierówności rekurencyjnej, często są to jednak metody nieefektywne lub numerycznie niestabilne. Zazwyczaj zadowalające jest rozwiązanie asymptotyczne.

Przykład

[edytuj | edytuj kod]

Przykładem równania rekurencyjnego liniowego jednorodnego jest równanie postaci

gdzie dane jest

Załóżmy, że ma ono rozwiązanie postaci Podstawiając otrzymujemy:

Dzieląc przez

Równanie to nazywamy równaniem charakterystycznym równania rekurencyjnego. W tym przypadku jest to równanie kwadratowe.

Jeżeli nie ma ono pierwiastków podwójnych, wówczas

Jeżeli natomiast równanie charakterystyczne ma pierwiastek podwójny, to

i są dowolnymi stałymi a i są pierwiastkami równania charakterystycznego. Jeżeli dane jest i wówczas można łatwo ułożyć układ równań i otrzymać ich wartość.

Przykład (ciąg Fibonacciego)

[edytuj | edytuj kod]

Następujący przykład jest rozwiązaniem ciągu Fibonacciego:

Warunki początkowe:

Równanie charakterystyczne ma następującą postać:

Pierwiastki tego równania są następujące:

Pierwiastki są różne, zatem:

Korzystając z warunków początkowych, układamy układ równań:

Z rozwiązania tego układu wynika:

Co po podstawieniu i do wzoru na otrzymujemy tzw. wzór Bineta:

Zobacz też

[edytuj | edytuj kod]